package org.hot100_1;

import org.leetcode.TreeNode;

public class leetcode49 {


    //hard
    int max =Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {

        if (root.left==null && root.right==null){
            return root.val;
        }
        dfs(root);
        return max;
    }

    public int dfs(TreeNode root) {
        if (root==null){
            return 0;
        }

        int leftPathSum = dfs(root.left);
        int rightPathSum = dfs(root.right);
        leftPathSum = Math.max(leftPathSum,0);
        rightPathSum=Math.max(rightPathSum,0);

        int currPathSum = root.val+leftPathSum+rightPathSum;
        max= Math.max(currPathSum,max);

        return Math.max(leftPathSum,rightPathSum)+root.val;
    }
}
